package main

import (
	"fmt"
)

/*
*
- 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组
是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
*/
func main() {
	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	fmt.Println(maxSubArray(nums))
}

func maxSubArray(nums []int) int {
	//return V1(nums)
	return V2(nums)
}

/**
 *	dp
 */
func V1(nums []int) int {
	N := len(nums)
	//	dp[i] 表示以i结尾（含i）的子和
	dp := make([]int, N)
	dp[0] = nums[0]
	mx := dp[0]
	for i := 1; i < N; i++ {
		dp[i] = max(dp[i-1]+nums[i], nums[i])
		mx = max(mx, dp[i])
	}
	return mx
}

/**
 *	dp[i]只和dp[i - 1]相关，所以用prev代替dp
 */
func V2(nums []int) int {
	N := len(nums)
	prev := nums[0]
	mx := prev
	for i := 1; i < N; i++ {
		v := max(prev+nums[i], nums[i])
		mx = max(mx, v)
		prev = v
	}
	return mx
}
